#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int MAXS = 1<<20;

int n,m,sum[MAXS],f[20][MAXS],lg[MAXS];
vector<pii> G[20];

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in;int all = 1 << n;
	for(int i = 1;i <= m;i++){
		int x = in-1,y = in-1,w = in;
		G[x].pb(pii(y,w)); G[y].pb(pii(x,w));
	}
	for(int i = 2;i < 1<<20;i<<=1) lg[i] = lg[i>>1] + 1;
	for(int i = 1;i < all;i++){
		int x = lg[i & -i]; int tot = 0;
		for(pii d : G[x]){
			if((i >> d.fi) & 1) tot += d.se;
		}
		sum[i] = sum[i ^ (1<<x)] + tot;
	} memset(f,0xcf,sizeof(f));
	f[0][1] = 0;
	for(int i = 1;i < all;i+=2)
		for(int x = 0;x < n;x++)
			if(!(all >> x & 1) && f[x][i] >= 0){
				for(pii d : G[x]){
					int y = d.fi,w = d.se;
					if(!(i >> y & 1))
						f[y][i | (1<<y)] = max(f[y][i | (1<<y)],f[x][i] + w);
				}
				int S = (all - 1) ^ i;
				for(int s = S;s;s = S & (s-1)){
					f[x][i | s] = max(f[x][i | s],f[x][i] + sum[s|(1<<x)]);
				}
			}
	printf("%d\n",sum[all-1]-f[n-1][all-1]);		
	return 0;
}

